class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        for i in range(1, x//2 + 1):
            if i**2 <= x < (i+1)**2:
                return i


# 二分法--不要求精度
def func_bi(x: int) -> int:
    left, right, result = 0, x, -1

    while left <= right:
        mid = (left + right) // 2
        if mid * mid <= x:
            result = mid
            left = mid + 1
        else:
            right = mid - 1
    return result


# 二分法--要求精度为 1e-7
def func_bi_acc(x: int) -> int:
    left, right, result = 0, x, -1

    while left <= right:
        mid = (left + right) // 2
        if abs(x - mid * mid) > 1e-7:
            result = mid
            left = mid + 1
        else:
            right = mid - 1
    return result


# 牛顿迭代法
def func_newton(x: int) -> int:
    if x == 0:
        return 0

    C, x0 = float(x), float(x)
    while True:
        xi = 0.5 * (x0 + C / x0)
        if abs(x0 - xi) < 1e-7:  # 误差范围
            break
        x0 = xi
    return int(x0)


if __name__ == '__main__':
    t = 704810419
    # x = Solution()
    # print(x.mySqrt(t))
    # print(func_bi(t))
    print(func_bi_acc(t))
    # print(func_newton(t))
